前置知识
笛卡尔积
对于两个集合 X,YX, YX,Y，定义它们的笛卡尔积为 X×Y={(x,y)∣x∈X,y∈Y}X \times Y = \{(x, y) \mid x \in X, y \in Y\}X×Y={(x,y)∣x∈X,y∈Y}。
对于任意集合 AAA，定义 A1=AA ^ 1 = AA1=A，An=An−1×A(n∈N,n>1)A ^ n = A ^ {n - 1} \times A(n \in \N, n > 1)An=An−1×A(n∈N,n>1)。
二元关系
对于两个集合 X,YX, YX,Y，定义 XXX 到 YYY 的二元关系 RRR 为 X×YX \times YX×Y 的子集。对于 x∈X,y∈Yx \in X, y \in Yx∈X,y∈Y，记 xRyx\mathrel{R}yxRy 当且仅当 (x,y)∈R(x, y) \in R(x,y)∈R。
如果 Y=XY = XY=X，则可以称 RRR 是 XXX 上的二元关系。
等价关系
对于集合 XXX 上的二元关系 RRR，定义其为等价关系，当且仅当其满足：
自反性（r...
问题概述
给你一个正整数 nnn（1≤n≤2×1051 \le n \le 2 \times 10 ^ 51≤n≤2×105），求一个长度为 nnn 的 01 串，使得其本质不同的子串数量在所有 2n2 ^ n2n 个长度为 nnn 的 01 串中最多。
答案上界
我们考虑字符串的长度 iii，显然在长度为 nnn 的字符串中，本质不同的长度为 iii 的字符串个数上界为 min{2i,n−i+1}\min\left\{2 ^ i, n - i + 1\right\}min{2i,n−i+1}，所以答案上界为 ∑i=1nmin{2i,n−i+1}\sum _ {i = 1} ^ n \min\left\{2 ^ i, n - i + 1\right\}∑i=1nmin{2i,n−i+1}。
对于 n = 2 ^ k + k - 1
这里我们引入一个名为 De Bruijn Graph 的特殊的有向图。
定义 De Bruijn Graph 为一个有 knk ^ nkn 个点的有向图，每个点为一个由 kkk 种元素组成的有序 nnn 元组。当且仅当两个点 u,vu, ...
希望不会咕咕咕……
有些题 LOJ 上没有就不写了。
JOISC 2014
Day1T1 バス通学
答案显然只能是以 111 为起点的边的起始时间。
考虑将每个点的出边按起始时间从大到小排序，则对于每个到达时间，可以走的边都是一个前缀。
我们考虑对于每个答案跑最短路，发现复杂度爆炸。
但是排序后前面的答案能走的边后面的答案一定能走，于是我们考虑在之前的基础上跑最短路。具体地，我们对于每个点记录一个指针表示当前枚举到了第几条出边，显然指针之前的边没必要重新走一遍。这样每条边至多被使用一次，时间复杂度为 O(mlogm)O(m \log m)O(mlogm)。
最后对于每组询问二分即可得到答案。
提交记录
Day1T2 たのしい家庭菜園
显然最终序列一定是先一段单调不降再一段单调不升。
对于没有相同元素的情况，有一个显然的贪心：每次将最小的元素移到最左或最右（选择距离较短的），然后变成一个子问题。
考虑维护每个元素的实际位置，则移到最左对应前缀 +1+ 1+1，移到最前对应后缀 −1- 1−1，树状数组维护即可。
对于有相同元素的情况，每次移动距离最短的那个即可。
提交记录
...
符号及基本定义及约定
整除、取模、质数、算术基本定理等的定义。这部分直接 skip 了。
以下无特殊说明则默认变量为正整数，函数为数论函数。
以下用 P\mathbb{P}P 表示素数集合。
数论函数
定义域为正整数的函数被称为数论函数。
积性函数
若数论函数 f(x)f(x)f(x) 满足对于任意 a⊥ba \bot ba⊥b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为积性函数。
若数论函数 f(x)f(x)f(x) 满足对于任意 a,ba, ba,b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为完全积性函数。
性质
若 f(x)f(x)f(x) 和 g(x)g(x)g(x) 均为积性函数，则以下函数也是积性函数。
h(x)=f(xp)h(x) = f(x ^ p)h(x)=f(xp)。
h(x)=fp(x)h(x) = f ^ p(x)h(x)=fp(x)。
h(x)=f(x)g(x)h...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。
CF1137C Museums Tour [!]
tags: 图论, Tarjan, 拓扑排序\verb|tags: 图论, Tarjan, 拓扑排序|tags: 图论, Tarjan, 拓扑排序
建分层图，然后缩点，对于每个强连通分量求出其中有多少个地方。
然后直接拓扑排序求最长路就是答案。
问题在于为什么同一天不会被重复统计。
发现天数是循环的，也就是说如果某个城市第 xxx 天和第 x+yx + yx+y 天不在同一个强连通分量里，且能从第 xxx 天到达第 x+yx + yx+y 天，那一定能从第 x+yx + yx+y 天到达第 x+2yx + 2yx+2y 天，以此类推，一定能到达 (x+dy) mod d=x(x + dy) \bmod d = x(x+dy)modd=x 天，所以 xxx 和 x+yx + yx+y 一定在同一个强连通分量里。
CF1137E Tr...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。
CF1037G A Game on Strings [!!!]
观察发现，如果某次我选择了字符 ccc，则剩下的子串要么左边是 ccc，要么右边是 ccc。
也就是说，对于每个字符 ccc，设其出现的位置为 posc,1,posc,2,…,posc,kpos _ {c, 1}, pos _ {c, 2}, \ldots, pos _ {c, k}posc,1,posc,2,…,posc,k，那么有用的串就是所有 sposc,i,posc,i+1s _ {pos _ {c, i}, pos _ {c, i + 1}}sposc,i,posc,i+1 及其所有前缀和后缀。这样的串的个数为 O(n∣Σ∣)O(n \left|\Sigma\right|)O(n∣Σ∣)。
我们考虑预处理出所有有用的串的 SG 函数。
考虑将所有串按长度排序，对于每个串暴力转移。
很可惜，这样复杂...
打算系统性地学习和复习一下字符串算法。
一些算法内容比较多会拆到别的文章里。
符号与约定
首先让我们形式化地定义一下字符串的各个概念。
字符集为一个建立了全序关系的集合，用符号 Σ\SigmaΣ 来表示。其中的元素被称为字符。
字符串 sss 是一个由若干字符按顺序排列而成的序列。
下文默认字符串下标从 111 开始。
定义 sis_isi 表示字符串 sss 的第 iii 个字符。
定义 ∣s∣\left|s\right|∣s∣ 为字符串 sss 的长度。
空串即为不包含任何字符，∣s∣=0\left|s\right| = 0∣s∣=0 的字符串。
我们定义字符与字符、字符与字符串、字符串与字符、字符串与字符串之间的拼接表示将这两个字符或字符串按顺序拼在一起得到的字符串，写作 s+ts + ts+t 或 ststst。sks^ksk 表示 kkk 个 sss 拼接。
字符串 sss 的一个子串 s[l,r]s_{[l, r]}s[l,r] 表示 sl,sl+1,…srs_l, s_{l + 1}, \ldots s_{r}sl,sl+1,…sr 按顺序连接得到的字符...
感觉最近越来越摆了。
所以打算记录一下做到的好题。
联合省选 2023 Day1 T2 城市建造
称额外修建的道路连接的城市为标记点，容易发现任意两个标记点之间的边都必须是额外修建的道路。
题目要求在删除新增的道路后任意两个标记点不连通，所以对于任意一个点双，如果标记了两个点，则必须标记其余所有点。
关于为什么不是边双：
然后进一步观察发现，删除的点双必须是连通的。
于是考虑建圆方树 DP。
然后求助了 djwj233。
首先对于 k=0k = 0k=0，块的大小必须是 nnn 的因数，只有 O(n)O(\sqrt{n})O(n) 个。
对于 k=1k = 1k=1，块的大小只可能是 ⌊ns⌋\left\lfloor\dfrac{n}{s}\right\rfloor⌊sn⌋ 或 ⌈ns⌉\left\lceil\dfrac{n}{s}\right\rceil⌈sn⌉（其中 sss 为任意正整数），简单分析发现也只有 O(n)O(\sqrt{n})O(n) 种。
于是可以考虑枚举块的大小 BBB，再进行 DP。
我们发现树上连通块一定有一个深度最小的点，且其他点都在它的子...
Problem
洛谷 P7987 [USACO21DEC] Paired Up G
题目大意：
有 nnn 个点，其中第 iii 个点位置为 xix_ixi，权值为 yiy_iyi。若两个点 i,ji, ji,j 满足 ∣xi−xj∣≤k|x_i - x_j| \le k∣xi−xj∣≤k，则这两个点之间有一条边。
求一个匹配，在满足其为极大匹配的情况下匹配点的权值和最大/最小。
求总权值和与匹配点的权值和的差。
Solution
提供一种不同于洛谷题解区的解法。
结论：作为答案的匹配中的任意两对匹配 (a,b)(a, b)(a,b) 和 (c,d)(c, d)(c,d)，区间 [a,b][a, b][a,b] 与区间 [c,d][c, d][c,d] 一定不交。
这个可以用调整法证明。如果两个匹配 (a,b)(a, b)(a,b) 和 (c,d)(c, d)(c,d) 满足 a<c<b<da < c < b < da<c<b<d，则可以将匹配调整成 (a,c)(a, c)(a,c) 和 (b,d)(b, d)(b...